public class board {
    public static int minRobots(int[][] checkerboard) {
        int m = checkerboard.length;
        if (m == 0) return 0;
        int n = checkerboard[0].length;
        int count = 0;

        while (true) {
            boolean hasCoins = false;
            int i = 0, j = 0;

            while (i < m && j < n) {
                if (checkerboard[i][j] > 0) {
                    hasCoins = true;
                    checkerboard[i][j] = 0;
                }
                if (j + 1 < n && (i + 1 >= m || sumRight(checkerboard, i, j) >= sumDown(checkerboard, i, j))) {
                    j++;
                } else {
                    i++;
                }
            }

            if (!hasCoins) {
                break;
            }
            count++;
        }
        return count;
    }

    // 计算当前位置右侧剩余硬币总数
    private static int sumRight(int[][] board, int i, int j) {
        int sum = 0;
        for (int k = j + 1; k < board[0].length; k++) {
            sum += board[i][k];
        }
        return sum;
    }

    // 计算当前位置下侧剩余硬币总数
    private static int sumDown(int[][] board, int i, int j) {
        int sum = 0;
        for (int k = i + 1; k < board.length; k++) {
            sum += board[k][j];
        }
        return sum;
    }

    public static void main(String[] args) {
        int[][] checkerboard = {
                {0, 0, 0, 0,0,0,0,0},
                {0, 0, 0, 0,0,1,0,0},
                {0, 0, 1, 0,0,0,0,0},
                {0, 0, 0, 1,0,1,0,0},
                {0,0,1,0,0,1,0,0},
                {0,0,0,0,0,0,0,1},
                {0,0,0,0,0,0,0,0},
                {0,0,0,0,0,1,1,0}
        };
        System.out.println(minRobots(checkerboard));
    }
}


